package com.wuyou.dataStructure.tree;

import org.springframework.dao.CleanupFailureDataAccessException;

import java.util.*;

/**
 * 层序遍历
 * 根-左-右
 * 根(左)-左-右
 */
public class LevelOrder {


    public static void main(String[] args) {
        System.out.println(5/2);
        System.out.println(5/2+5%2);
    }

    /**
     * 前序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> sol_2(TreeNode root){
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        int level = 0; // 当前层数
        order(root, ans, level);
        return ans;
    }

    private void order(TreeNode root, List<List<Integer>> ans, int level){
        if (root == null) {
            level --;
            return;
        }
        if (ans.size() < level + 1) { // 是否有这一层
            ans.add(new LinkedList<>());
        }
        ans.get(level).add(root.val);
        order(root.left, ans, level+1);
        order(root.right, ans, level+1);
    }

    /**
     * 一层一层打印-BFS(广度优先遍历) Breath First Search
     * DFS Depth First Search
     *
     * @param root
     * @return
     */
    public List<List<Integer>> sol_1(TreeNode root){
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 每层的节点数量
            int levelNum = queue.size();
            // 存储每层节点值
            List<Integer> subList = new ArrayList<>();
            for(int i=0;i<levelNum;i++){
                // 出队
                TreeNode node = queue.poll();
                subList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            ans.add(subList);
        }
        return ans;
    }



}
